package problem;

import java.util.HashMap;
import java.util.Map;

/**
 * <p>
 *  给定一个链表，每个节点包含一个额外增加的随机指针，该指针可以指向链表中的任何节点或空节点。
 *
 * 要求返回这个链表的 深拷贝。 
 *
 * 我们用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示：
 *
 * val：一个表示 Node.val 的整数。
 * random_index：随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为  null 。
    思路1：1）复制新节点到源节点的后面，2）复制随机指针，3）链表拆分开
    思路2：使用哈希表，key存放原节点，value存放新节点
 * </p>
 *
 * @author fangXK
 * @since 2020-08-10
 */
public class S_138 {
    /*
// Definition for a Node.
     */
class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}

    class Solution {
        public Node copyRandomList(Node head) {
            if(head==null) return null;
            Node p=head;
            //1.在每个原节点后面创建一个新的节点
            //1->1'->2->2'->3->3'
            while(p!=null){
                Node newNode=new Node(p.val);
                newNode.next=p.next;
                p.next=newNode;
                p=newNode.next;
            }
            //复制完后重置头节点指针p
            p=head;
            //2.设置新节点的随机节点
            while(p!=null){
                if(p.random!=null) p.next.random=p.random.next;
                p=p.next.next;
            }
            //复制完后重置头节点指针p
            p=head;
            //设置一个虚假的头节点
            Node dummy=new Node(-1);
            Node cur=dummy;
            //3.将两个链表分开
            while(p!=null){
                cur.next=p.next;
                cur=cur.next;
                p.next=p.next.next;
                p=p.next;
            }
            return dummy.next;
        }

        public Node copyRandomList1(Node head){
            if(head==null) return null;
            //1.创建一个哈希表，key是原节点，value是新节点
            Map<Node,Node> map=new HashMap<>();
            Node p=head;
            //2.将原节点和新节点放入哈希表中
            while(p!=null){
                Node newNode=new Node(p.val);
                map.put(p,newNode);
                p=p.next;
            }
            //重置p为头节点
            //3.遍历原链表，设置新节点的next和random
            while(p!=null){
                Node newNode=map.get(p);
                if(p.next!=null) newNode.next=map.get(p.next);
                if(p.random!=null) newNode.random=map.get(p.random);
                p=p.next;
            }
            return map.get(head);
        }
    }
}
